package learn.binarysearch;

/**
 * 二分查找之： 不定长的边界
 *  有一段不知道具体长度的日志文件，里面记录了每次登陆的时间戳，
 *  已知日志是按顺序从头到尾记录的，没有记录日志的地方为空。那么当前日志的长度是多少
 *
 *  二分搜索做法：
 *      一开始 low = 0; high = 1;
 *      只要logs[high] != null，high = high * 2
 *      当logs[high]为null的时候，可以在取区间[0,high]进行普通的二分查找
 *
 *  小结：
 *      在不确定边界时，先确定边界再进行二分查找
 */
public class Demo1 {
    int low = 0,high = 1;

    /**
     * 确定上边界
     * @param logs
     * @param high
     * @return
     */
    int getUpperBound(String[] logs,int high) {
        if (logs[high] == null){
            return high;
        }
        return getUpperBound(logs,high*2);
    }

    /**
     * 进行二分查找
     */
    int binarySearch(String[] logs,int low,int high) {
        //判断low high是否合法
        if (low > high) {
            return -1;
        }

        //判断是否找到
        int middle = low + (high - low) / 2;
        if (logs[middle] == null && logs[middle-1] != null) {
            return middle;
        }

        //二分查找
        if (logs[middle] == null){
            //middle为空则在左边进行查找
            return binarySearch(logs,low,middle-1);
        }else {
            return binarySearch(logs,middle+1,high);
        }
    }


}
